package leetcode.editor.cn;
public class P1143LongestCommonSubsequence {
    public static void main(String[] args) {
        Solution solution = new P1143LongestCommonSubsequence().new Solution();
        
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestCommonSubsequence(String s, String t) {
        //sLength和tLength分别是两个字符串的长度
        int sLength = s.length();
        int tLength = t.length();
        int[][] dp = new int[tLength + 1][sLength + 1];

        for (int i = 1; i <= tLength; i++) {
            for (int j = 1; j <= sLength; j++) {
                //下面是递推公式
                if (t.charAt(i - 1) == s.charAt(j - 1)) {
                    //如果字符串t的第i个字符和s的第j个字符一样，
                    //那么有两种选择
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    //如果字符串t的第i个字符和s的第j个字符不一样，
                    //我们只能用字符串s的前j-1个字符来计算他包含的数量
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[tLength][sLength];

    }
}
//leetcode submit region end(Prohibit modification and deletion)

}